package com.test.demo;

import com.sun.jmx.remote.internal.ArrayQueue;
import org.apache.commons.lang3.StringUtils;

import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 01背包，用一维数组存储
 */

public class Main {
    private static int findMax(int number, int capacity, int[] w, int[] v) {
        int[] s = new int[capacity + 1];
        for(int i = 1; i<= number; i++) {
            for(int j=capacity; j>=0; j--) {
                if (j - w[i] >= 0 && s[j] <= s[j - w[i]] + v[i]) {
                    s[j] = s[j - w[i]] + v[i];
                }
            }
        }
        return s[capacity];
    }

    public static void main(String[] args) {
        MyQueue que = new MyQueue();
        que.pushBack(73);
        que.pushBack(74);
        que.pushBack(60);
        System.out.println(que.maxValue());
        que.pushBack(80);
        System.out.println(que.maxValue());
        que.popFront();
        System.out.println(que.maxValue());
        que.popFront();
        que.popFront();
        que.popFront();
        System.out.println(que.maxValue());
    }

    private static class MyQueue {
        private int[] elements = new int[1024];
        private int takeIndex;
        private int putIndex;

        private int[] sorted = new int[1024];
        private int tailIndex;
        private int headIndex;

        public int maxValue() {
            return sorted[tailIndex-1];
        }

        public void pushBack(int i) {
            if (tailIndex == 0 || sorted[tailIndex] < i) {
                sorted[tailIndex++] = i;
            }
            elements[putIndex++] = i;
        }

        public void popFront() {
            int i = elements[takeIndex];
            if (i == sorted[headIndex]) {
                headIndex++;
            }
            takeIndex++;
        }
    }
}
